package problem222_Count_Complete_Tree_Nodes;

import problem108_Convert_Sorted_Array_to_Binary_Search_Tree.TreeNode;

public class Solution {
	 public int countNodes(TreeNode root) {
		if(root==null)	return 0;
		int count=1,left=leftMost(root.left),rightsLeft=leftMost(root.right);
		if(left==rightsLeft){
			count+=(1<<left)-1;
			count+=countNodes(root.right);
		}else{
			count+=(1<<rightsLeft)-1;
			count+=countNodes(root.left);
		}
		return count;
	 }
	 
	 private int leftMost(TreeNode node){
		 int count=0;
		 while(node!=null){
			 count++;
			 node=node.left;
		 }
		 return count;
	 }
}
